用 JavaScript 实现栈

发表于   |   分类于

栈是一种遵从后进先出（LIFO）原则的有序集合。新添加的或待删除的元素都保存在栈的末尾，称作栈顶，另一端就叫做栈底。在栈里，新元素都靠近栈顶，旧元素都靠近栈底。

简单点来说，类似于餐厅里面堆放的盘子，先放进来的盘子放在最底下，最后面放进来的盘子堆在最上面，洗的时候从最顶上的盘子开始洗，也就是后面来的先洗。

栈的创建

我们将创建一个类来表示栈：

1
2
3
functin Stack(){
    // 各种属性和方法的声明
}

首先，我们需要一种数据结构来保存栈里的元素。可以选择数组：

1
var items = [];

接下来，要为我们的栈声明一些方法：

  • push(element(s)):添加一个（或几个）新元素到栈顶；
  • pop():移除栈顶的元素，同时返回被移除的元素；
  • peek():返回栈顶的元素，不对栈做任何修改；
  • isEmpty():如果栈里没有任何元素就返回true，否则返回false；
  • clear():移除栈里所有的元素；
  • size():返回栈里的元素个数，类似数组里的length属性。

最后实现的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
function Stack(){
	var items = [];

	this.push = function(element){
		items.push(element);
	};

	this.pop = function(){
		return items.pop();
	};

	this.peek = function(){
		return items[items.length - 1];
	};

	this.isEmpty = function(){
		return items.length == 0;
	}

	this.size = function(){
		return items.length;
	}

	this.clear = function(){
		items = [];
	};

	this.print = function(){
		console.log(items.toString());
	}
}

为了检查栈里的内容，我添加了一个辅助的print方法，用来输出栈里的内容。

使用栈

创建完这个Stack，接下来就要用它来解决一些实际的问题。

十进制转化为二进制

要把十进制转化为二进制，可以将该十进制数字和2整除，直到结果为0。举个例子，把十进制的数字10转化为二进制的数字，过程大概是这样的：

Markdown

实现的算法如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function divideBy2(decNumber){
	var remStack = new Stack(),s, rem, binaryString = '';

	while(decNumber>0){
		rem = Math.floor(decNumber%2);
		remStack.push(rem);
		decNumber = Math.floor(decNumber/2);
	}

	while(!remStack.isEmpty()){
		binaryString += remStack.pop().toString();
	}

	return binaryString;
}

注意：JavaScript有数字类型，但是它不会区分究竟是整数还是浮点数。因此要使用Math.floor函数让除法的操作仅返回整数部分。

只要修改一下算法，就能把十进制转化成任何进制：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
function baseConverter(decNumber, base){

    var remStack = new Stack(),
        rem,
        baseString = '',
        digits = '0123456789ABCDEF';

    while (decNumber > 0){
        rem = Math.floor(decNumber % base);
        remStack.push(rem);
        decNumber = Math.floor(decNumber / base);
    }

    while (!remStack.isEmpty()){
        baseString += digits[remStack.pop()];
        //String[index]返回字符串在制定位置上的字符
    }

    return baseString;
}

检测括号是否匹配

实现函数：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
function matches(open, close){
    var opens = "([{",
        closers = ")]}";
    return opens.indexOf(open) == closers.indexOf(close);
    //确保匹配到正确的括号
}

function parenthesesChecker(symbols){

    var stack = new Stack(),
        balanced = true,
        index = 0,
        symbol, top;

    while (index < symbols.length && balanced){
        symbol = symbols.charAt(index);
        //str.charAt(index)返回字符串在指定位置上的字符
        if (symbol == '('|| symbol == '[' || symbol == '{'){
            stack.push(symbol);
        } else {
            if (stack.isEmpty()){
                balanced = false;
            } else {
                top = stack.pop();
                //最后添加到数组中的括号要最先进行匹配
                if (!matches(top, symbol)){
                    balanced = false;
                }
            }
        }
        index++;
    }
    if (balanced && stack.isEmpty()){
        return true;
    }
    return false;
}

检测一下:

1
2
console.log(parenthesesChecker('{{([][])}()}'));    //true
console.log(parenthesesChecker('[{()]'));   //false

不过这个代码还需要改进一下才有实际的用处，因为：

1
console.log(parenthesesChecker('[{("hello")]'));   //false

实际运用当中可以用来检测用户输入的数据当中是否含有未匹配的括号。